#include <algorithm>
#include <iostream>
using namespace std;
#include <vector>

class Solution
{
public:
    static string addBinary(string a, string b)
    {
        string rs;
        int carry = 0;
        int i = a.size()-1, j = b.size()-1;
        while(carry || i>=0 || j>=0)
        {
            int num1 = i>=0 ? a[i]-'0' : 0;
            int num2 = j>=0 ? b[j]-'0' : 0;
            int sum = num1 + num2 + carry;
            carry = sum/2;
            rs += sum%2+'0';
            i--;
            j--;
        }
        reverse(rs.begin(), rs.end());
        return rs;
    }
};